package com.mlh.matrix;

import java.util.Arrays;

/**
 * @author 缪林辉
 * @date 2024/8/19 15:01
 * @DESCRIPTION
 */
//给定一个 m x n 的矩阵，如果一个元素为 0 ，则将其所在行和列的所有元素都设为 0 。请使用 原地 算法。
//    输入：matrix = [[1,1,1],[1,0,1],[1,1,1]]
// 输出：[[1,0,1],[0,0,0],[1,0,1]]
public class 矩阵置零 {
    //使用两个标记变量
    // 思路和算法
    // 我们可以用矩阵的第一行和第一列代替方法一中的两个标记数组，以达到 O(1) 的额外空间。
    // 但这样会导致原数组的第一行和第一列被修改，无法记录它们是否原本包含 0。
    // 因此我们需要额外使用两个标记变量分别记录第一行和第一列是否原本包含 0。
    // 在实际代码中，我们首先预处理出两个标记变量，接着使用其他行与列去处理第一行与第一列，
    // 然后反过来使用第一行与第一列去更新其他行与列，最后使用两个标记变量更新第一行与第一列即可。
    public void method1(int[][] matrix) {
        int rowLen=matrix.length,colLen=matrix[0].length;
        boolean firstRow=false,firstCol=false;
        //设置标记变量
        for (int i = 0; i < rowLen; i++) {
            if (matrix[i][0]==0){
                firstCol=true;
                break;
            }
        }
        for (int i = 0; i < colLen; i++) {
            if(matrix[0][i]==0){
                firstRow=true;
                break;
            }
        }
        //利用第一列和第一行标记其他位置的0
        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }
        //利用第一列和第一行标记来赋值0
        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                if (matrix[i][0] == 0 || matrix[0][j] == 0) {
                    matrix[i][j] = 0;
                }
            }
        }
        //通过标记变量来给第一行和第一列赋值
        if(firstRow){
            for (int i = 0; i < colLen; i++) {
                matrix[0][i]=0;
            }
        }
        if(firstCol){
            for (int i = 0; i < rowLen; i++) {
                matrix[i][0]=0;
            }
        }
    }
    public void practice(int[][] matrix) {
        int rowLen=matrix.length,colLen=matrix[0].length;
        boolean rowZero=false,colZero=false;
        for (int i = 0; i < rowLen; i++) {
            if(matrix[i][0]==0){
                rowZero=true;
                break;
            }
        }
        for (int i = 0; i < colLen; i++) {
            if(matrix[0][i]==0){
                colZero=true;
                break;
            }
        }
        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                if(matrix[i][j]==0){
                    matrix[i][0]=0;
                    matrix[0][j]=0;
                }
            }
        }

        for (int i = 1; i < rowLen; i++) {
            for (int j = 1; j < colLen; j++) {
                if(matrix[i][0]==0||matrix[0][j]==0){
                    matrix[i][j]=0;
                }
            }
        }
        if(rowZero){
            for (int i = 0; i < rowLen; i++) {
                matrix[i][0]=0;
            }
        }
        if(colZero){
            for (int i = 0; i < colLen; i++) {
                matrix[0][i]=0;
            }
        }
    }
    
}
